package datasorter;

import org.apache.log4j.Logger;

public class CountingSort extends DataSorter<Integer> {
	private static final Logger log = Logger.getLogger(CountingSort.class);
	public Integer[] sort(Integer[] data) {
		if (data == null)
			return null;
		if (data.length == 0 || data.length == 1)
			return data;
		sort(data, 0, data.length);
		return data;
	}

	public Integer[] sort(Integer[] data, SortType type) {
		if (data == null)
			return null;
		if (data.length == 0 || data.length == 1)
			return data;
		if (SortType.DESC.equals(type))
			reverse(data);
		return data;
	}

	/**
	 * Sort elements of input array 
	 * @param data input array of data
	 * @param low left position of array
	 * @param high right position of array
	 */
	private void sort(Integer[] data, int low, int high) {
		int[] counts = new int[high - low + 1];
		log.info("Extra memory-"+counts.length);
		for (int x : data)
			counts[x - low]++;
		int current = 0;
		for (int i = 0; i < counts.length; i++) {
			fill(data, current, current + counts[i], i + low);
			current += counts[i];
		}
	}

	/**
	 * Assigns the specified  value to each element of the specified range of the specified array.
	 * @param a specified array
	 * @param fromIndex start position
	 * @param toIndex end position
	 * @param val specified value
	 */
	private void fill(Integer[] a, int fromIndex, int toIndex, int val) {
		for (int i = fromIndex; i < toIndex; i++)
			a[i] = val;
	}
}
